Search results for "Graph product"
showing 6 items of 6 documents
On the Toeplitz algebras of right-angled and finite-type Artin groups
1999
The graph product of a family of groups lies somewhere between their direct and free products, with the graph determining which pairs of groups commute and which do not. We show that the graph product of quasi-lattice ordered groups is quasi-lattice ordered, and, when the underlying groups are amenable, that it satisfies Nica's amenability condition for quasi-lattice orders. As a consequence the Toeplitz algebras of these groups are universal for covariant isometric representations on Hilbert space, and their representations are faithful if the isometries satisfy a properness condition given by Laca and Raeburn. An application of this to right-angled Artin groups gives a uniqueness theorem …
Incremental bipartite drawing problem
2001
Abstract Layout strategies that strive to preserve perspective from earlier drawings are called incremental. In this paper we study the incremental arc crossing minimization problem for bipartite graphs. We develop a greedy randomized adaptive search procedure (GRASP) for this problem. We have also developed a branch-and-bound algorithm in order to compute the relative gap to the optimal solution of the GRASP approach. Computational experiments are performed with 450 graph instances to first study the effect of changes in grasp search parameters and then to test the efficiency of the proposed procedure. Scope and purpose Many information systems require graphs to be drawn so that these syst…
Algorithms on Graphs
1988
In this chapter we shall develop some basic algorithms for directed graphs and relations which will be of use in later chapters, where the efficient construction of parsers is considered. The constructions needed can be expressed as the computing of certain “relational expressions”. These are expressions whose operands are relations and whose operators are chosen from among multiplication, closure, union and inverse. For this purpose we need to develop an algorithm for computing the closure of a relation. In view of the nature of our applications, the most appropriate way to do this is by a depth-first traversal of the graph that corresponds to the given relation. Other ways of computing th…
Radio k-Labelings for Cartesian Products of Graphs
2005
International audience; Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that |f(x)−f(y)| ≥ k+1−dG(x,y), for any two vertices x and y, where dG(x,y) is the distance between x and y in G. The radio k-chromatic number is the minimum of max{f(x)−f(y):x,y ∈ V(G)} over all radio k-labelings f of G. In this paper we present the radio k-labeling for the Cartesian pro…
Tabu search for the dynamic Bipartite Drawing Problem
2018
Abstract Drawings of graphs have many applications and they are nowadays well-established tools in computer science in general, and optimization in particular. Project scheduling is one of the many areas in which representation of graphs constitutes an important instrument. The experience shows that the main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion to achieve it. Incremental or dynamic graph drawing is an emerging topic in this context, where we seek to preserve the layout of a graph over successive drawings. In this paper, we target the edge crossing reduction in the context of incremental graph drawing. Specifically…
Vertex Distinguishing Edge- and Total-Colorings of Cartesian and other Product Graphs
2012
International audience; This paper studies edge- and total-colorings of graphs in which (all or only adjacent) vertices are distinguished by their sets of colors. We provide bounds for the minimum number of colors needed for such colorings for the Cartesian product of graphs along with exact results for generalized hypercubes. We also present general bounds for the direct, strong and lexicographic products.